1. Field of the Invention
The present invention relates to a mesh network bridge, and in particular to a mesh network bridge connected by line to a mesh network configured of a plurality of bridges interconnected by line, and including the shortest path constructing means such as the optimized forwarding and a plurality of mesh-connecting ports.
2. Description of the Related Art
As one form of network, there is a mesh network including a plurality of bridges interconnected by line.
Among the mesh networks of this kind, a full-mesh network (hereinafter referred to as FMN) including a plurality of bridges all interconnected by line with at least one line between the bridges is well known.
FIG. 23 shows an example of FMN of this kind.
A bridge connected in mesh is called the mesh network bridge.
The network connected in mesh is described as a mesh domain for distinction from the other parts.
Also, the mesh domain connected in full mesh is sometimes described as a FMN domain.
As shown in FIG. 24, each mesh network bridge 32 includes mesh-connecting ports 33 for mesh connection and non-mesh-connecting ports 34.
The mesh-connecting port 33 is used for line connection with other mesh network bridges 32.
The non-mesh-connecting port 34, on the other hand, is connected with nodes 37 and bridges 36 for constructing an external network other than the mesh network bridge 32.
In a network containing a redundant route caused by a plurality of bridges, a spanning tree protocol (STP) is employed for determining a route.
For example, as shown in FIG. 25, assume a network over which LAN 1 and LAN 2 are connected to each other by means of a bridge A.
Here, in the case of a network over which node “n1” such as personal computer is connected to LAN 1, and HUB 1 is connected to LAN 2, packets transmitted from the node “n1” are transmitted to all nodes of a broadcast domain including node “n2” such as personal computer connected to the HUB 1 via LAN 1→bridge A→LAN 2→HUB 1.
Over such network, when HUB 2 is connected to LAN 1 and LAN 2 in parallel to bridge A, a packet transmitted from the node “n1” loops over the network like LAN 1→bridge A→LAN 2→HUB 2→LAN 1→bridge A→LAN 2→HUB 2. As a result, a packet cannot be transmitted from a node other than node “n1” (node in a broadcast domain other than node “n1”).
In the case where a network is configured by only bridge A and HUB 1 as shown in FIG. 25, a spanning tree is employed to prevent a packet transmitted from a node from looping over the network.
In addition, as shown in FIG. 26, in the case where two bridges A and B are connected in parallel between LAN 1 to which node “n1” such as personal computer is connected and LAN 2 to which HUB 1 is connected, thereby making communication among nodes “n2”, “n3”, “n4”, . . . such as personal computers connected to node “n1” and HUB 1, one bridge is generally used to make communication. When this bridge A is linked down, the other bridge B is used to make communication, whereby a spanning tree is employed in order to cause a network to provide redundancy.
Here, basic algorithm and protocol of the spanning tree includes the following items (1) to (5) (Refer to ISO/IEC 15802-3: 1998 (E) ANSI/IEEE Std 80 2. 1D, 1998 Edition, Part 3: Media Access Control(MAC) Bridges, pp v-xix, LOCAL AND METROPOLITAN AREA NETWORKS: 8. the Spanning Tree Algorithm and Protocol pp. 58-109 and 9. Encoding of Bridge Protocol Data Units(BPDUs) pp. 110-113).
(1) A special frame called Configuration Bridge Protocol Data Units (hereinafter, referred to as BPDU) is exchanged between bridges.
The following works are performed based on this exchanged BPDU.
(2) A network root bridge is selected.
Only one root bridge exists in the entire LAN bridge connected.
(3) Each bridge computes the shortest route that reaches a root bridge (A port that provides the shortest route to the root bridge is called a root port).
(4) With respect to each LAN, a “designated bridge” is selected from a bridge connected to the LAN.
(5) Each bridge selects a port (designated port) that belongs to a spanning tree and a port (blocked port) that does not belong to such spanning tree.
All data frames received at a blocked port are discarded.
In addition, frame transmission from a blocked port is not performed at all.
A received BPDU is not forwarded at all.
A data portion of the above mentioned BPDU includes at least root ID, bridge ID, root path cost.
Root ID is an ID of a root bridge (or a bridge assumed to be such root bridge), and is generated based on a MAC address of such bridge and a priority designated by an administrator.
Bridge ID is an ID of a bridge that transmits a BPDU, and is generated based on a MAC address of such bridge and a priority designated by an administrator.
A root path cost is a cost of the (possible) shortest route from a bridge that transmits a BPDU to a root bridge.
In an initial state (when a power is supplied), each bridge is a root bridge itself, and it is assumed that a root path cost is 0.
Each bridge transmits the initial value of a BPDU to all ports, and at the same time, receives the BPDU transmitted from another bridge from all the ports.
In the case where a bridge has received a better BPDU from a port, such bridge stops transmission of BPDU to that port, and then, changes the value of the BPDU to be transmitted by the bridge itself.
In this manner, in the case where a spanning tree enters a stable state, only one bridge transmits a BPDU among each LAN.
For example, in the case where BPDU 1 and BPDU 2 are present, it is judged which of the above BPDUs is better in accordance with rules (1) to (4) below. (1) In the case where root ID of BPDU 1 is numerically smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
(2) In the case where root ID of BPDU 1 is numerically equal to that of BPDU 2, if a root path cost of BPDU 1 is smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
(3) In the case where root ID of BPDU 1 is numerically equal to that of BPDU 2, and a root path cost of BPDU 1 is equal to that of BPDU 2, if bridge ID of BPDU 1 is numerically smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
(4) In the case where root ID of BPDU 1 is numerically equal to that of BPDU 2, a root path cost of BPDU 1 is equal to that of BPDU 2, and bridge ID of BPDU 1 is numerically equal to that of BPDU 2, if port ID of BPDU 1 is smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
Then, each bridge compares the initial value of its own BPDU with that of the BPDU from another bridge received from all ports, and selects root ID from the best BPDU.
Next, each bridge computes its own root path cost in accordance with (root path cost)=(root path cost in the best BPDU)+path cost.
A path cost is a cost to the root that each port individually has, and the value of the cost can be set by an administrator.
Once a root ID, a route port, and a root path cost are defined, each bridge updates the content of BPDU transmitted by such each bridge itself.
Further, its own updated BPDU is compared with BPDU received from a port other than root port, and it is judged whether or not each port other than root port is a designated bridge itself.
A port that is a designated bridge is called a designated port, and a port that is not a designated bridge is called a blocked port.
In BPDU transmission and data frame forwarding to a root port, a designated port and a blocked port, a data frame is forwarded at the root port without transmitting BPDU; BPDU is transmitted, and a data frame is forwarded at the designated port; and BPDU is not transmitted, and a data frame is not forwarded at the blocked port.
In this manner, once a spanning tree is configured, each bridge performs regular operations described in (1) to (4) below.
These regular operations are required for reconfiguring a spanning tree that has been configured due to a bridge fault or addition of new bridge.
(1) BPDU includes an element called “message age”.
This value denotes an elapsed time after a root bridge has generated a BPDU that corresponds to the above BPDU.
(2) A root bridge transmits its own BPDU periodically to all ports. At this time, “message age” is set to 0.
(3) Each bridge stores a received BPDU, and increases the value of the “message age” of the BPDU stored in each port with an elapse of time (message age timer).
(4) A bridge other than root bridge transmits its own BPDU when it receives a BPDU from a root port.
At this time, as a value of the “message age”, there is used a value equal to or greater than the “message age” of the root port and greater than the “message age” of the received BPDU.
Here, the reconfiguration of the spanning tree occurs in any of the cases described in (1) and (2) below.
(1) In the case where the “message age” timer of the stored BPDU times out (in the case where a max age is exceeded); or
(2) In the case where a BUDU better than that stored in a port or a BPDU with the small value of the message age is received from the same port.
In the case where any of the above events occurs, a bridge performs re-computation for a root ID, a root path cost, and a root port.
In the meantime, it is very dangerous to perform data frame transmission before all the bridges over a network enters a normal state after configuration (reconfiguration) of a spanning tree has been started.
This is because there is a possibility that a temporary loop occurs during spanning tree configuration.
Therefore, even if each bridge determines its own designated port, it does not start data frame forwarding immediately.
There are four types of the states of each port in a bridge:
(1) listening: No work concerning a data frame is carried out.
(2) learning: Although the learning of a starting MAC address is performed, forwarding is not performed.
(3) forwarding: Data frame forwarding is performed.
(4) disable: This state completely stops the port and does not perform receiving and transmitting of all packets.
The lengths of the listening state and learning state are called a “forward delay”. A root bridge determines its value, enters its value in a BPDU, and transmits the fact to each bridge.
In addition, a timer employed in the listening state and learning state is called a “forwarding timer”.
If spanning tree reconfiguration occurs, a host position changes, and the contents of an old forwarding table may be incorrect.
Thus, the bridge corresponding to a spanning tree has two kinds of states as timeout values of the forwarding table aging timer as follows.
(1) Normal value: This value is set to a long time such as a few minutes.
(2) A value used after topology change: This value is the same as the forward delay value.
When a bridge senses spanning tree reconfiguration, the timeout value of the forwarding table aging timer is set to a value identical to forward delay for a predetermined period of time.
In the meantime, a spanning tree algorithm and protocol has a system that notifies to all bridges that spanning tree reconfiguration has occurred.
(1) When a bridge senses a topology change, that bridge transmits a frame called TCN-BPDU (Topology Change Notification BPDU) to a root port with hello time intervals.
This transmission is continued until a BPDU in which a TCA (Topology Change Acknowledgment) flag is set has been received from the root port.
(2) A bridge which has received TCN-BPDU also transmits TCN-BPDU to its own root port.
On the other hand, to a port that has received a TCN-BPDU, a BPDU TCA flag is set, and a BPDU is transmitted during transmission of the next BPDU.
(3) In the case where a root bridge receives a TCN-BPDU or the state of its own port changes, the root bridge transmits a BPDU in which a TC (Topology Change) flag is set from that time to a max age+forward delay time.
(4) A bridge which has received the TC flag set BPDU from a root port sets a TC flag for its own BPDU, and transmits such BPDU.
This transmission is continued until a BPDU in which a TC flag is not set has been received.
(5) While a bridge receives TC flag set BPDU from the root port, the bridge uses the value of “forward delay” as a timeout value of the forwarding table aging timer.
In this way, a spanning tree has an algorithm for automatically removing a loop in a redundant bridge network, and automatically sensing a network topology change caused by a device fault or cable failure, thereby automatically changing a network topology so as to prevent a loop from being produced.
In the network configuration using the spanning tree protocol according to ANSI/IEEE Std 802.1D described above, a blocked port is automatically produced thereby to avoid a loop of the network and to use a loop-free route.
However, in the case where the network configuration using the spanning tree according to ANSI/IEEE Std 802.1D described above is employed for FMN as shown in FIG. 27, for example, the problem is posed that a route not necessarily optimum for FMN is formed.
FIG. 27 shows an example of a network configuration (same as FIG. 23) using the spanning tree according to ANSI/IEEE Std 802.1D described above for FMN.
In FIG. 27, the bridges a, b, c constitute mesh network bridges 32.
In the network configuration shown in FIG. 27, the bridge a constitutes a root bridge, and the port near to the bridge d between the bridge b and the bridge d, the port near to the bridge c between the bridge b and the bridge c, and the port near to the bridge d between the bridge c and the bridge d are each set as a blocked port according to the spanning tree protocol.
In the network configuration shown in FIG. 27, therefore, the route for communication from the node a to the node b passes not through the shortest one including the bridge e, the bridge d and the bridge b, but through the bridge e, the bridge d, the bridge a and the bridge b.
Thus, the communication route from the node a to the node b constitutes a detour in the network configuration shown in FIG. 27. As compared with the communication through the shortest path, therefore, the problem of a longer communication time is posed.
Also, this conventional network configuration encounters the problem that an excessive load is imposed on a part of the nodes.
In the case of the network configuration shown in FIG. 27, for example, a blocked port is set by the spanning tree protocol, and therefore, the communication between bridges always passes through the root bridge a. This not only imposes an excessive load on the bridge a, but an extraneous load on a part of lines, thereby leading to the problem that the lines cannot be used efficiently and the line utilization rate is reduced.
Further, the problem of extraneous charge is posed in the case where the mesh network described above is constructed on the Internet and the Ethernet (R) frame is passed through the Internet using L2TP (Layer2 Tunneling Protocol).
L2TP is a means for transmitting the L2 frame of Ethernet or PPP to the Internet in the form encapsulated in IP.
In the case where the mesh network shown in FIG. 27 is constructed on the Internet, for example, the communication from the node a to the node b passes through two routes, one from the mesh network bridge d to the mesh network bridge a, and the other from the mesh network bridge a to the mesh network bridge b. Thus, charge accrues twice and doubles.
In order to obviate this problem and optimize the forwarding in FMN, there has been proposed a method utilizing the optimized forwarding with an improved network configuration using the spanning tree according to ANSI/IEEE Std 802.1D described above for communication between the FMN bridges in CE-based Virtual Private LAN (http://www.ietf.org/internet-draft/draft-lee-ce-based-vpl-00.txt).
This method utilizing the optimized forwarding presupposes no spanning tree operation.
The communication between bridges in this method utilizing the optimized forwarding uses the following algorithms (1) to (4) to secure the shortest path on FMN free of the loop.
(1) The unicast packet received from a FMN connecting port is flooding to all the non-FMN connecting ports but not to the FMN connecting ports.
(2) The multicast packet received from a FMN connecting port is multicasting to all the non-FMN connecting ports but not to the FMN connecting ports.
(3) The unicast packet received from a non-FMN connecting port is flooding to all the FMN connecting ports and all the non-FMN connecting ports.
(4) The multicast packet received from a non-FMN connecting port is multicasting to all the FMN connecting ports and all the non-FMN connecting ports.
In the case of (4), it is recommended that IGMP Snooping be used at the same time to avoid the unnecessary distribution for a further improvement of the line efficiency.
In the case of communication between the bridge c and any other bridge (the bridge a, the bridge b or the bridge d) by the aforementioned method of the optimized forwarding employed for FMN shown in FIG. 23, the bridge that has received a packet from the bridge c does not flood the particular packet to other mesh network bridges.
As a result, the communication between bridges using the method of the optimized forwarding for FMN causes no delay by detour and can be established through the shortest path, thereby leading to the advantage of obviating the problem of the network configuration using the spanning tree of ANSI/IEEE Std 802.1D.
Even in the case where the method of the optimized forwarding is employed for FMN, however, the problem described below is still encountered.
Specifically, in view of the fact that the method using the optimized forwarding described above presupposes no spanning tree operation, no redundant route can be used even in case of a line fault in the communication between bridges.
In the network configuration shown in FIG. 28, for example, assume that the communication between from the node c to the node b develops a line fault between the bridge b and the bridge c. Packets from the node c are flooded to the bridge a and the bridge d. Packets received by the bridge a or the bridge d, however, are not flooded to the bridge b.
Even in the case where a line fault occurs between the bridge b and the bridge c, therefore, no redundant route can be used and the packets from the node c cannot be sent to the node b.
Also, as shown in FIG. 29, in the case where new bridges f and g are added to form a backup route between the bridge a and the bridge c, a loop is formed by the bridge a, the bridge c, the bridge f and the bridge g.
However, in the method of using the optimized forwarding described above, which presupposes no operation of the spanning tree, a loop, if formed in a route on the network, cannot be detected to set a blocking port.
The network shown in FIG. 29, therefore, poses the problem that in the case where a loop is formed on a route on the network, a packet sent out from a given node would undesirably flow through the route forming the loop, thereby reducing the line efficiency.